// list.c
// 线性表

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct list
{
    // 数据-数组
    int *data;
    // 容量
    int capacity;
    // 大小
    int size;
} List;

void init(List *l, int n);
void add(List *l, int v);
void show(List *l);
void insert(List *l, int index, int v);
void list_incr(List *l);
// int get(List *l, int index);
// int find(List *l, int value);
// void delete(List *l, int index);
// int size(List *l);
// bool empty(List *l);
// void clear(List *l);


int main(int argc, char const *argv[])
{
    List *li = malloc(sizeof(struct list));
    // 初始化
    init(li, 3);
    // 添加元素
    add(li, 100);
    add(li, 200);
    add(li, 300);
    add(li, 400);
    add(li, 500);
    add(li, 600);
    add(li, 700);
    show(li);
    // 任意位置插入
    insert(li, 3, 2333);
    // 显示
    show(li);
    return 0;
}

void init(List *l, int n)
{
    l->capacity = n;
    l->size = 0;
    l->data = malloc(sizeof(int) * n);
}
void list_incr(List *l)
{
    // 增量
    int incr = l->capacity << 1;
    l->capacity += incr;
    printf("扩容至：%d\n", l->capacity);
    // 扩容
    l->data = realloc(l->data, sizeof(int) * l->capacity);
}
// O(1)
void add(List *l, int e)
{
    // 满了？
    if (l->capacity == l->size)
    {
        list_incr(l);
    }
    
    l->data[l->size] = e;
    l->size++;
}

void show(List *l)
{
    for (size_t i = 0; i < l->size; i++)
    {
        printf("[%ld]=%d,", i, l->data[i]);
    }
    printf("\n");
}

void insert(List *l, int index, int v)
{
    // 插入位置是否有效
    if (index > l->size)
        return;

    if (l->size == l->capacity)
    {
        // 扩容
        list_incr(l);
    }
    for (int i = l->size - 1; i >= index; i--)
    {
        l->data[i + 1] = l->data[i];
    }
    l->data[index] = v;
    l->size++;
}
